package com.example.leetcode;

import com.example.leetcode.entity.TreeNode;

import java.util.LinkedList;

/**
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例:
 *
 * 给定二叉树 [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回它的最小深度  2.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode_111 {

    /**
     *  深度优先算法
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        int minDepth = Integer.MAX_VALUE;
        if (root.left != null){
            minDepth = Math.min(minDepth(root.left),minDepth);
        }
        if (root.right != null){
            minDepth = Math.min(minDepth(root.right),minDepth);
        }
        return minDepth + 1;
    }


    /**
     *广度优先算法
     *
     *
     */
    public int minDepth2(TreeNode root) {
        if (root == null) return 0;

        LinkedList<DepthNode> depthNodes = new LinkedList<>();
        depthNodes.add(new DepthNode(root,1));
        if (!depthNodes.isEmpty()){
            DepthNode depthNode = depthNodes.poll();
            TreeNode node = depthNode.node;
            if (node.left == null && node.right == null){
                return depthNode.depth;
            }
            if (node.left != null){
                depthNodes.add(new DepthNode(node.left,depthNode.depth+1));
            }

            if (node.right != null){
                depthNodes.add(new DepthNode(node.right,depthNode.depth+1));
            }

        }
        return 0;
    }

    class DepthNode{
        public TreeNode node;
        public int depth;

        public DepthNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

}
